﻿//#define TRACE_1
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions.Problems
{
    /*
     * The most naive way of computing n15 requires fourteen multiplications:

n × n × ... × n = n15

But using a "binary" method you can compute it in six multiplications:

n × n = n2
n2 × n2 = n4
n4 × n4 = n8
n8 × n4 = n12
n12 × n2 = n14
n14 × n = n15

However it is yet possible to compute it in only five multiplications:

n × n = n2
n2 × n = n3
n3 × n3 = n6
n6 × n6 = n12
n12 × n3 = n15

We shall define m(k) to be the minimum number of multiplications to compute nk; for example m(15) = 5.

For 1 ≤ k ≤ 200, find ∑ m(k).

     * */
    class Problem122 : IProblem
    {
        public string Calculate()
        {
            Dictionary<int, List<List<int>>> values = new Dictionary<int, List<List<int>>>();
            values.Add(2, new List<List<int>>() { new List<int>() { 1 } });
            values.Add(3, new List<List<int>>() { new List<int>() { 2, 1 } });
            values.Add(4, new List<List<int>>() { new List<int>() { 2, 1 }, new List<int>() { 3, 2, 1 } });

            int limit = 200;
            long sum = 0;

            for (int i = 5; i <= limit; i++)
            {
                values.Add(i, new List<List<int>>());

                for (int j = 1; j <= i / 2; j++)
                {
                    int rem = i - j;
                    foreach (var list in values[rem])
                    {
                        if (list.Contains(j) || rem == j)
                        {
                            List<int> temp = new List<int>(list);
                            temp.Insert(0, rem);
                            values[i].Add(temp);
                        }
                    }

                    int min = values[i].Select(x => x.Count).Min();
                    sum += min;
                    values[i] = values[i].Where(x => x.Count == min).ToList();
                }
            }

            
#if TRACE_1
            for (int i = 2; i <= limit; i++)
            {
                int min = values[i].Select(x => x.Count).Min();
                var q = values[i].Where(x => x.Count == min).ToList();

                Console.WriteLine("power: {0}, minimum multiplications: {1}, count: {2}", i, min, q.Count);

                foreach (var list in q)
                {
                    foreach (int v in list)
                    {
                        Console.Write("{0} ", v);
                    }
                    Console.WriteLine();
                }
                Console.WriteLine();
            }
#endif

            return sum.ToString();
        }
    }
}
